package com.排序.插入.直插;

import java.util.Arrays;

/**
 * the class of algorithm
 *
 * 直接插入排序是指将一个个待排序的元素插入到前面已经排好序的有序序列中去，直到插完所有元素为止，主要步骤如下：
 *
 * 1）先假设第一个元素已经排好序。
 *
 * 2）然后依次取出还需要进行排序的下一个元素，设为待插入元素，在已经排序的元素序列中从后向前扫描，如果该元素（已排序）大于待插入元素，将该元素移到下一位置。
 *
 * 3）重复步骤2，直到找到已排序的元素小于或者等于待排序元素的位置，插入元素。
 *
 * 4）重复步骤2、步骤3，完成排序。
 *
 *
 * 总结： 先把待插入元素取出(从数组下标1开始，因为只有一个元素的数组就是一个有序数组)
 *          那么数组当前位置就是空的，接下来的操作就是：
 *             a.之前比waitSort大的元素就可以往后移动一位,
 *             b.再把waitSort往前移动一位。
 * <p>
 * .
 *
 * @author little_lunatic
 * @date 2022-12-14
 */
public class InLineSort {
    public static void main(String[] args) {
        int[] arr = {9, 8, 0, 6, 10, 5, 4, 3, 2, 1};
        int[] arr2 = {9, 1};
        int[] arr3 = null;
        inlineSort(arr);
        inlineSort(arr2);
        inlineSort(arr3);
        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(arr2));
        System.out.println(Arrays.toString(arr3));
    }

    private static void inlineSort(int[] arr) {
        if (arr == null) {
            return;
        }

        for (int i = 1; i < arr.length; i++) {
            int waitSort = arr[i];
            for (int j = i-1; j >=0 ; j--) {
                if (waitSort < arr[j]){
                    arr[j+1] = arr[j];
                    arr[j] = waitSort;
                }
            }
        }
    }

}